import java.util.*;

public class Test {
    //
    public static void main(String[] args) {
        //
    }
}

class Solution
{
    Map<Character, Set<Character>> edges = new HashMap<>(); // 邻接表
    Map<Character, Integer> in = new HashMap<>(); // 统计每个节点的⼊度
    boolean check;
    public String alienOrder(String[] words)

  {
    // 1. 初始化⼊度哈希表 + 建图
    for(String s : words)
    {
        for(int i = 0; i < s.length(); i++)
        {
            char ch = s.charAt(i);
            in.put(ch, 0);
        }
    }
    int n = words.length;
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            add(words[i], words[j]);
            if(check == true) return "";
        }
    }
    // 2. 拓扑排序
    Queue<Character> q = new LinkedList<>();
    for(char ch : in.keySet())
    {
        if(in.get(ch) == 0) q.add(ch);
    }
    StringBuffer ret = new StringBuffer();
    while(!q.isEmpty())
    {
        char t = q.poll();
        ret.append(t);
        if(!edges.containsKey(t)) continue;
        for(char ch : edges.get(t))
        {
            in.put(ch, in.get(ch) - 1);
            if(in.get(ch) == 0) q.add(ch);
        }
    }
    // 3. 判断
    for(char ch : in.keySet())
    {
        if(in.get(ch) != 0) return "";
    }
    return ret.toString();
   }
    public void add(String s1, String s2)
    {
        int n = Math.min(s1.length(), s2.length());
        int i = 0;
        for( ; i < n; i++)
        {
            char c1 = s1.charAt(i), c2 = s2.charAt(i);
            if(c1 != c2)
            {
                // c1 -> c2
                if(!edges.containsKey(c1))
                {
                    edges.put(c1, new HashSet<>());
                }
                if(!edges.get(c1).contains(c2))
                {
                    edges.get(c1).add(c2);
                    in.put(c2, in.get(c2) + 1);
                }
                break;
            }
        }
        if(i == s2.length() && i < s1.length()) check = true;
    }
}
